package design;

import org.omg.CORBA.INTERNAL;

import java.util.HashMap;

public class LRU_146_7 {
    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int cap;
    public LRU_146_7(int capacity) {
        this.cap = capacity;
        map= new HashMap<>(capacity);
        cache = new DoubleList();

    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        makeRecently(key);

        return node.v;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            deleteKey(key);
            addRecently(key,value);
            return;
        }
        if(cap == cache.size){
            removeLeastRecently();
        }
        addRecently(key,value);

    }

    private void makeRecently(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }
    private void addRecently(int key, int value){
        Node x = new Node(key,value);
        cache.addLast(x);
        map.put(key,x);
    }

    private void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    private void removeLeastRecently(){
        Node removeFirst = cache.removeFirst();
        map.remove(removeFirst.k);
    }



    class DoubleList{
        private Node head;
        private Node tail;
        private int size;

        public DoubleList(){
            head = new Node(0,0);
            tail = new Node(0,0);
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        public void addLast(Node x){
            x.pre = tail.pre;
            x.next = tail;
            tail.pre.next = x;
            tail.pre = x;
            size++;
        }

        public void remove(Node x){
            x.pre.next = x.next;
            x.next.pre = x.pre;
            size--;
        }

        public Node removeFirst(){
            if(head.next == tail){
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }

        public int size(){
            return size;
        }



    }
    class Node{
        private int k;
        private int v;
        public Node pre;
        public Node next;
        public Node(int k, int v){
            this.k = k;
            this.v = v;
        }
    }
}
